/*******************************************************************************
 * Copyright (c) 2000, 2017 IBM Corp. and others
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution and
 * is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following
 * Secondary Licenses when the conditions for such availability set
 * forth in the Eclipse Public License, v. 2.0 are satisfied: GNU
 * General Public License, version 2 with the GNU Classpath
 * Exception [1] and GNU General Public License, version 2 with the
 * OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] http://openjdk.java.net/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
 *******************************************************************************/

#ifndef STRINGBUILDERTRANSFORMER_INCL
#define STRINGBUILDERTRANSFORMER_INCL

#include <stdint.h>
#include "infra/ILWalk.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/OptimizationManager.hpp"

namespace TR { class Block; }

/** \brief
 *
 *  Transforms StringBuilder constructor calls to preallocate a heuristically determined capacity for
 *  StringBuilder objects generated by idiomatic Java String concatenation operations.
 *
 *  \details
 *
 *  The Java Language Specification for the String Concatenation Operator + (Section 15.18.1) states
 *  that for a sequence of String concatenation operations a Java compiler implementation may choose to
 *  use a StringBuilder to reduce the number of intermediate String objects that are created by evaluation
 *  of an expression.
 *
 *  A canonical example is concatenating a String object and an integer. In such cases a StringBuilder will
 *  always be used as it allows appending arbitrary object types. The Java bytecode compiler will
 *  typically translate the following String concatenation operation:
 *
 *  String result = "test" + 1 + '2';
 *
 *  into the following sequence:
 *
 *  String result = (new StringBuilder ()).append("test").append(1).append('2').toString();
 *
 *  Although the Java Language Specification does not dictate which StringBuilder constructor overload is
 *  invoked, many Java bytecode compilers will chose to invoke the default constructor for which the Java Class
 *  Library dictates that it must allocate an initial buffer capacity of 16 chars.
 *
 *  When the chain of appends exhausts the StringBuilder's capacity the StringBuilder will reallocate a larger
 *  buffer to make room for the incoming append object. Unfortunately the StringBuilder implementation will at
 *  least double the size of it's buffer when a reallocation is needed. This could potentially result in many
 *  allocated bytes being unused. Note that the upon a reallocation the StringBuilder will also have to copy
 *  the contents of its current buffer into the new enlarged buffer, thus incurring an additional cost.
 *
 *  The realization here is that for compile time constants we can statically determine the size of the final
 *  resulting String at compile time. We can then use this information to transform the StringBuilder default
 *  constructor call to an overloaded constructor call accepting an initial capacity which we computed at compile
 *  time. The end result is an overall reduction in the number of reallocations that the StringBuilder will perform.
 *
 *  This optimization searches for these StringBuilder chained append calls followed by a toString and it
 *  heuristically tries to estimate the sizes of the append arguments. If it can the optimization will precisely
 *  determine the sizes of all constant append arguments.
 *
 *  \section Debug Counters
 *
 *  You can track the locations of where this optimization succeeded or failed via the following debug counter:
 *
 *  -Xjit:staticDebugCounters={StringBuilderTransformer*}
 *
 *  \section Environment Variables
 *
 *  The optimization provides 5 environment variables to collect various statistics on the locations in which this
 *  optimization can be performed. The environment variables displayed below require a modified StringBuilder.java
 *  implementation to collect the various statistics. The source of the modified StringBuilder.java is attached to
 *  Work Item 122287 in which this optimization was delivered. When using the below environment variables you must
 *  make sure the new StringBuilder.class is prepended to the bootclasspath when invoking the JVM. Upon JVM shutdown
 *  the statistics will be printed to stdout.
 *
 *  export TR_StringBuilderTransformerCollectAppendStatistics=1;
 *
 *  This environment variable tracks the char size of the argument to append and for each size it tracks the number
 *  of such objects that passed through the respective append call. This statistic is collected for each overload of
 *  StringBuilder.append(...) that this optimization supports. The output will be a per overload sequential sorted
 *  list of append char lengths delimited by a comma with the count of the number of times the respective append
 *  overload was invoked with a value of the specified char length.
 *
 *  export TR_StringBuilderTransformerCollectAllocationStatistics=1;
 *
 *  This environment variable tracks the total number of allocated chars from all call sites in which this optimization
 *  was performed. The output will be the total number of chars that all the StringBuilders have allocated.
 *
 *  export TR_StringBuilderTransformerCollectAllocationBacktraces=1;
 *
 *  This environment variable tracks the back traces of all call sites that this optimization was performed on. The
 *  output will be a sorted back trace of the call site along with the invocation count.
 *
 *  export TR_StringBuilderTransformerCollectAppendObjectTypes=1;
 *
 *  This environment variable tracks the types of the arguments supplied to the StringBuilder.append(Object) overload.
 *  The output will be a list of append char lengths delimited by a comma with the count of the number of times the
 *  StringBuilder.append(Object) overload was invoked an object of the specified char length. This statistic will be
 *  displayed per object type.
 *
 *  export TR_StringBuilderTransformerOverrideInitialCapacity=###;
 *
 *  This environment variable can be used to override the final capacity that this optimization has heuristically
 *  calculated with the ### supplied.
 */
class TR_StringBuilderTransformer : public TR::Optimization
   {
   public:

   /** \brief Initializes the StringBuilderTransformer optimization.
    *
    *  \param manager The optimization manager.
    */
   TR_StringBuilderTransformer(TR::OptimizationManager* manager)
      : TR::Optimization(manager)
      {
      // Void
      }

   /** \brief Helper function to create an instance of the StringBuilderTransformer optimization using the
    *         OptimizationManager's default allocator.
    *
    *  \param manager The optimization manager.
    */
   static TR::Optimization* create(TR::OptimizationManager* manager)
      {
      return new (manager->allocator()) TR_StringBuilderTransformer(manager);
      }

   /** \brief Performs the optimization on this compilation unit.
    *
    *  \return 1 - if any transformation was performed.
    *          0 - if no transformations were performed.
    */
   virtual int32_t perform();

   /** \brief Performs the optimization on a specific block within this compilation unit.
    *
    *  \param block The block on which to perform this optimization.
    *
    *  \return 1 - if any transformation was performed.
    *          0 - if no transformations were performed.
    */
   virtual int32_t performOnBlock(TR::Block* block);

   virtual const char * optDetailString() const throw()
      {
      return "O^O STRINGBUILDER TRANSFORMER: ";
      }

   private:

   /** \brief Attempts to find a call to the StringBuilder.<init>() constructor whose receiver is \p newNode.
    *
    *  \param iter The iterator to begin searching from.
    *  \param newNode A TR::New node which is the receiver of the constructor call we are searching for.
    *
    *  \return The call to StringBuilder.<init>() or NULL if the call was not found.
    */
   TR::Node* findStringBuilderInit(TR::TreeTopIterator iter, TR::Node* newNode);

   /** \brief Attempts to find and collect the arguments of a sequence of chained StringBuilder.append(...) calls
    *         which is terminated by a call to StringBuilder.toString().
    *
    *  \param iter The iterator to begin searching from.
    *  \param newNode A TR::New node which is the receiver of the first chained StringBuilder.append(...) call.
    *  \param appendArguments If this function returns non-NULL this out parameter contains an ordered list of all the arguments
    *         of the sequence of chained StringBuilder.append(...) calls.
    *
    *  \return The call to StringBuilder.toString() or NULL if the call was not found or if the
    *          StringBuilder.append(...) chain was broken.
    */
   TR::Node* findStringBuilderChainedAppendArguments(TR::TreeTopIterator iter, TR::Node* newNode, List<TR_Pair<TR::Node*, TR::RecognizedMethod> >& appendArguments);

   /** \brief Given a list of arguments of a sequence of chained StringBuilder.append(...) calls outputs the
    *         heuristically calculated char length of the String that is the result of a call to StringBuilder.toString().
    *
    *  \param appendArguments A list of arguments of a sequence of chained StringBuilder.append(...) calls.
    *
    *  \return Heuristically calculated char length of the String that is the result of a call to StringBuilder.toString().
    */
   int32_t computeHeuristicStringBuilderInitCapacity(List<TR_Pair<TR::Node*, TR::RecognizedMethod> >& appendArguments);
   };

#endif
